//
// Created by xili on 2024/8/7 21:32.
// Go big or go home.
//
#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
    int largestInteger(int num) {
        priority_queue<int> odd;
        priority_queue<int> even;
        vector<int> v;
        while (num) {
            int t = num % 10;
            v.push_back(t);
            if ((t & 1) == 0) {
                even.push(t);
            } else {
                odd.push(t);
            }
            num /= 10;
        }
        int ans = 1;
        for (int i = v.size() - 1; i >= 0; i--) {
            if ((v[i] & 1) == 0) {
                ans = ans * 10 + even.top();
                even.pop();
            } else {
                ans = ans * 10 + odd.top();
                odd.pop();
            }
        }
        return ans;
    }
};